package example.反转世界.链表反转;

public class Demo1 {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        if (m == 1 && n == 1) {
            return head;
        }
        //head开头的反转
        if (m == 1) {
            ListNode nn = head;
            //获取第n个节点
            for (int i = 1; i < n; i++) {
                nn = nn.next;
            }
            //先保存n+1节点
            ListNode nnnext = nn.next;
            //再断开n+1节点
            nn.next = null;
            //head-n个节点的反转
            ListNode node = revList(head);
            ListNode newNode = node;
            ListNode ccPrev = null;
            while (node != null) {
                ccPrev = node;
                node = node.next;
            }
            ccPrev.next = nnnext;
            return newNode;
        }
        //非head开头的反转
        ListNode current = head;
        for (int i = 2; i < m; i++) {//1-m 的到是 m-prev
            current = current.next;
        }
        // m-1的节点
        ListNode mPrevNode = current;
        // m的节点
        ListNode mNode = current.next;
        for (int i = m; i <= n; i++) {
            current = current.next;
        }
        //n的节点
        ListNode nNode = current;
        //先记录--n+1节点
        ListNode nNextNode = current.next;
        //断开需要反转的连续
        nNode.next = null;
        //反转m-n的节点之后的头节点
        ListNode node = revList(mNode);
        mPrevNode.next = node;
        ListNode ccPrev = null;
        while (node != null) {
            ccPrev = node;
            node = node.next;
        }
        ccPrev.next = nNextNode;
        return head;
    }

    public ListNode revList(ListNode head) {
        ListNode current = head, prev = null;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
